package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */


public class LC393 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        // input types: determined by most significant 1 ~ 5 bits
        final int TYPE_0 = 0b00000000;
        final int TYPE_1 = 0b10000000;
        final int TYPE_2 = 0b11000000;
        final int TYPE_3 = 0b11100000;
        final int TYPE_4 = 0b11110000;
        // masks for most significant 1 to 5 bis
        final int[] MASKS = new int[]{0b10000000, 0b11000000, 0b11100000, 0b11110000, 0b11111000};
        // input type enumation
        final int[] TYPES = new int[]{TYPE_0, TYPE_1, TYPE_2, TYPE_3, TYPE_4};
        // map of cur_stat : (input_type : next_stat)
        final Map<Integer, Map<Integer, Integer>> DFA = new HashMap<>();

        // build the dfa
        {
            Map<Integer, Integer> mp0 = new HashMap<>();
            Map<Integer, Integer> mp1 = new HashMap<>();
            Map<Integer, Integer> mp2 = new HashMap<>();
            Map<Integer, Integer> mp3 = new HashMap<>();
            Map<Integer, Integer> mp4 = new HashMap<>();
            Map<Integer, Integer> mp5 = new HashMap<>();
            Map<Integer, Integer> mp6 = new HashMap<>();

            mp0.put(TYPE_0, 0);
            mp0.put(TYPE_2, 1);
            mp0.put(TYPE_3, 2);
            mp0.put(TYPE_4, 3);

            mp1.put(TYPE_1, 0);
            mp2.put(TYPE_1, 4);
            mp4.put(TYPE_1, 0);
            mp3.put(TYPE_1, 5);
            mp5.put(TYPE_1, 6);
            mp6.put(TYPE_1, 0);

            DFA.put(0, mp0);
            DFA.put(1, mp1);
            DFA.put(2, mp2);
            DFA.put(3, mp3);
            DFA.put(4, mp4);
            DFA.put(5, mp5);
            DFA.put(6, mp6);
        }

        public boolean validUtf8(int[] data) {
            int cur = 0;
            for (int input : data) {
                Integer next = getNext(cur, input);
                if (next == null) {
                    return false;
                }
                cur = next;
            }
            return cur == 0;
        }

        private int getType(int in) {
            for (int i = 0; i < TYPES.length; i++) {
                if ((MASKS[i] & in) == TYPES[i]) {
                    return TYPES[i];
                }
            }
            // unreachable. unless input is "11111xxx" which is not a valid utf-8 character.
            return -1;
        }

        private Integer getNext(int cur, int input) {
            int type = getType(input);
            if (type == -1) return null;
            return DFA.get(cur).get(type);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[235, 140, 4]");
        System.out.println(solution.validUtf8(arr));
    }

    public static void main(String[] args) throws Exception {
        LC393 an = new LC393();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
